/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 这种方法完全利用了完全二叉树的特性，每一次的递归都派出了大约一般的节点，时间复杂度是O(log^2n)
// 其中n是节点数，这比直接遍历所有的节点的O(n)的复杂度要高
var countNodes = function (root) {
  if (root === null) {
    return 0;
  }

  // 计算树的高度（从0开始）
  let h = 0;
  let node = root;
  while (node.left !== null) {
    h++;
    node = node.left;
  }

  if (h === 0) {
    return 1;
  }

  // 计算右子树的高度
  let rightHeight = 0;
  node = root.right;
  while (node !== null) {
    rightHeight++;
    node = node.left;
  }

  // 如果右子树的高度等于h-1，说明左子树是满二叉树
  if (rightHeight === h - 1) {
    return (1 << h) + countNodes(root.right);
  } else {
    // 否则右子树是高度为h-2的满二叉树
    return (1 << (h - 1)) + countNodes(root.left);
  }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 但是这种直接遍历所有的节点的方式要简单
var countNodes = function (root) {
  if (root === null) {
    return 0;
  }

  // 递归计算左子树和右子树的节点数，加上根节点
  return 1 + countNodes(root.left) + countNodes(root.right);
};